COMMENT ⊗   VALID 00016 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00003 00002	.device xgp
C00005 00003	.begin center select 5
C00010 00004	A.  Merits of LISP.
C00018 00005	2.	LISP is efficient.  Another myth popular among non-LISP users
C00026 00006	3.	LISP uses a standard character set.  Essentially all
C00027 00007	4.	LISP is interactive.  If one wants to know the value of 1+1
C00029 00008	5.	LISP is modular.  One of the joys of programming in LISP is
C00035 00009	6.	LISP is notation-independent.  Mathematically speaking, LISP
C00058 00010	7.	LISP is applicative.  That is, one can write non-trivial
C00066 00011	8.	LISP is widely used in academia.  In a large portion of the
C00067 00012	9.	LISP is used by half the MIT Computer Science faculty.  Thus
C00069 00013	10.	No other language enjoys all the above advantages of LISP.
C00079 00014	B.  DRAWBACKS OF LISP.
C00087 00015	C.  DEPARTMENTAL REQUIREMENTS.
C00098 00016	.once center select 3
C00100 ENDMK
C⊗;
.device xgp
.sides←1;
.require "bask.pub[sub,sys]" source_file;
.font 5 "metlb";
.require "twocol.pub[sub,sys]" source_file;
.turn on "β" for "#";
.macro algol	⊂
.  at "begin"	⊂("%3bαegin%*")⊃;
.  at "end"	⊂("%3αeαnαd%*")⊃;
.  at "integer"	⊂("%3αiαnteger%*")⊃;
.  at "array"	⊂("%3αaαrray%*")⊃;
.  at "value"	⊂("%3αvαalue%*")⊃;
.  at "if"	⊂("%3αiαf%*")⊃;
.  at "then"	⊂("%3αtαhen%*")⊃;
.  at "procedure"	⊂("%3αpαrocedure%*")⊃;
.  at "for"	⊂("%3αfαor%*")⊃;
.  at "step"	⊂("%3αsαtep%*")⊃;
.  at "until"	⊂("%3αuαntil%*")⊃;
.  at "do"	⊂("%3αdαo%*")⊃;
.  at "go"	⊂("%3αgαo%*")⊃;
.  at "to"	⊂("%3αtαo%*")⊃;
.  ⊃
.onecol
.begin center; select 5
LISP - AN AMICUS CURIAE BRIEF
%3V. R. Pratt
1/10/77
.end;
.begin narrow 13,13;select 2;
.  fill nojust;
-- To the complexity of
building a single interface
between people, machines,
and problems, which has
made this brief so long.
.end
.skip 2
This position paper advances reasons in support of the
consideration of LISP as the language of choice for use within the
M.I.T. Electrical Engineering and Computer Science Department.  There
being no universally agreed on dialect of LISP to date, I have chosen
to describe MACLISP, the dialect implemented at MIT.  Even with such a
concrete object as an implementation there is room for interpretation
of what has been implemented.  Thus it must be realized that the
following represents one individual's perspective on one dialect of
LISP.
.BREAK
The paper is divided into three sections.  The first two
consider LISP %2in vacuo%*, without detailed reference to other languages
and without considering departmental needs.  The third section takes
into account what we need a programming language for.
.count page;
.every heading("%3LISP Brief",,{page!});
.twocol
A.  Merits of LISP.
.BREAK
There are ten sections below, with first sentences as follows.
.begin crbreak preface 0; indent 4,8;
1.	LISP is versatile.
2.	LISP is efficient.
3.	LISP uses a standard character set.
4.	LISP is interactive.
5.	LISP is modular.
6.	LISP is notation-independent.
7.	LISP is applicative.
8.	LISP is widely used in academia.
9.	LISP is used by half the MIT Computer Science faculty.
10.	No other language enjoys all the above advantages of LISP.
.end
1.	LISP is versatile.  Although LISP is caricatured by non-LISP
users as being of use mainly for manipulation of irregularly
structured data, this caricature does little justice to the careful
work done by McCarthy, Levin and others in the formative years of LISP
(around 1960) in developing a mathematically clean yet general
programming language.  Certainly Artificial Intelligence applications
were a concern during that development; after all, AI was the nutrient
medium within which LISP developed.  Yet the language has managed to
remain remarkably free of the concessions one might expect to arise
from such pressures, and is in our view one of the most
domain-independent languages currently enjoying wide usage.
.BREAK
We may illustrate LISP's versatility by reference to its data
types.  These are:
.begin indent 2,8; preface 0;crbreak
%2numbers%*	integers (unlimited size), reals
%2bit vectors%*	various applications, e.g. PASCAL's sets
%2booleans%*	T and NIL (for false)
%2atoms%*	serving double duty as strings and variables
%2lists%*	for which LISP is best known
%2property lists%*	various applications, e.g. PASCAL's records
%2arrays%*	unrestricted as to type or dimension
%2function(al)s%*	using LAMBDA and APPLY
%2programs%*	using EVAL and QUOTE
.end continue
In the MACLISP implementation the above data types are almost
"first-class citizens," a term used by the implementors of POP-2 [5]
to describe a data type that can be passed as a parameter, returned by
a function as a value, assigned to a variable, and tested for
equality.  LISP's data types include some for which equality cannot be
decided, namely the last two.  If we rule out the last requirement,
then all LISP data types are first-class citizens.
.BREAK
It is hard to appreciate what first-class citizenship really
means until one has programmed with and without it.  Now that I have
adopted a programming style which capitalizes on this asset of LISP, I
find that I have been able to clean up my programming style to the
point where I feel I am saying things the right way.  This is no more
than a generalization to other data types of the experience of a
generation of LISP programmers in writing programs that treat numbers
and lists as first-class citizens.  MACLISP has merely extended this
convenience to its other data types. For me to return to the situation
that obtains in, say, ALGOL or PASCAL, where an array-producing
subroutine must be given the array as input, would force me back to a
clumsy style that I now know is unnecessary. The same remark applies
to the other data types; for example the ability to pass property
lists around without requiring that they be attached to a particular
atom made it possible for me to implement the Boyer-Moore unification
algorithm in a cleaner way than Boyer and Moore implemented it.
.BREAK
For some, the data types FUNCTION and PROGRAM truly set LISP
apart from other languages.  To be precise, this power depends on
objects of these types being first-class citizens in the POP-2 sense.
This has certainly been the case for me.  For a number of years,
starting with the 1970 implementations of my LINGOL natural language
system and my CGOL syntactic front-end for LISP, I have built much of
my software around a central philosophy that is best described as
ACTOR-oriented [2].  I store information in small modules that can be
evaluated by LISP when they need to be queried.  The advantage of this
style is that such information can be made context-dependent because
like all LISP code it has access to the environment.  Moreover a
module can be "intelligent" about what it answers, possibly calling on
other modules for help before making up its mind.  Good examples of
how powerful this technique can be in practical situations can be
found in [7] and [8].  Carl Hewitt has built a whole programming
language based solely on this philosophy (which arose in his case out
of his earlier work on PLANNER) and has demonstrated how ACTORS can by
themselves supply the only foundations needed for a versatile and
efficient programming language, using methods analogous to the
corresponding demonstration for the pure lambda-calculus.
.skip;
2.	LISP is efficient.  Another myth popular among non-LISP users
is that to use LISP one resigns oneself to gross inefficiency.
To put this shibboleth to the test, members of the MACSYMA project
took some numerical benchmark programs of the sort that one would
normally think of as being well-suited to FORTRAN compilation, and
compared their running times under each of an (admittedly old) FORTRAN
compiler and the LISP compiler used at MIT on ITS [1].  Both
compilations were performed on the same machine, a PDP-10.  The LISP
compiler won!  With a little thought it becomes apparent that
inefficient object code does not inhere in a language but rather is
the result either of the program demanding something difficult such as
a complicated parameter-passing task, or of the compiler-writers not
doing a good job.  After all, why should the FORTRAN statement
.begin preface 0;indent 0,8;
βββA(I,J) = B(I,K)*C(K,J)
.break
and the LISP statement
.break
βββ(STORE (A I J) (TIMES (B I K) (C K J)))
.end continue
produce different object code?  In fact, in the experiment cited
above, the slight superiority of the LISP code (involving an
insignificant factor of about 1.2) was traceable not to the code
generated for the arithmetic parts of the program, which was almost
identical in each case, but rather to the more efficient procedure
calling in LISP.  This I feel convincingly disposes of the argument
that FORTRAN (and hence presumably most other high level languages) is
more appropriate when efficiency is needed.
.BREAK
Professor Bers group, which although in EECS is not a part of
the Computer Science laboratories (LCS and AI), does considerable
"number crunching," having used several hundred hours of computer time
for a variety of heavily numerical problems.  John L. Kulp of that
group has experimented with a few numerical problems using FORTRAN on
MULTICS and the 370/168, and LISP (under MACSYMA) on a PDP10 with a
KL-10 processor.  Although the arithmetic unit on the 168 has twice
the speed of that on the KL-10, that group has chosen to do most of
their work on the PDP-10 in LISP/MACSYMA, both because that factor of
two is considerably diluted by the associated and inevitable
non-numeric processing and because of the advantages of LISP over
FORTRAN.  (It should be noted that MACSYMA uses an algebraic notation,
removing any notational advantage FORTRAN may possess over the
standard LISP notation.)
.BREAK
This is not to say that one cannot write LISP programs that
are inefficient.  In a language as versatile as LISP it is inevitable
that the user will want to take advantage of constructs that
linguistically express perfectly what he is trying to say but
computationally present obstacles to efficient code generation.  Our
position on this is that the default should be that the programmer
feel no compunctions about using to the full the features of a
language, but that on those occasions when it truly is the case that
the machine's time is worth more than the programmer's (together with
the time of those who have to read his code) then the programmer
should know which constructions to avoid to permit the optimizer to do
as good a job with his code as a good FORTRAN optimizer can do.  Thus
a systems programmer writing widely used systems code in LISP might as
a general policy avoid heavy use of functions that do considerable
work to keep the environment in a consistent state such as code
associated with LISP's "special" variables.  (If one doubts that
efficient systems programming can be done in LISP, I should point to
the CGOL subsystem of LISP that I have developed to provide an
algebraic notation for MACLISP users, discussed in more detail in
section 6.  Users of this dialect sacrifice approximately a factor of
two in speed in reading their programs into LISP when they are running
those programs interpretively, and a negligible amount when they are
compiling their programs.  Some of this can be attributed to the
greater complexity of parsing an algebraic as opposed to a fully
parenthesized prefix notation, and the remainder to the fact that the
subsystem is written in LISP instead of assembly language.  I believe
a substantial proportion of this gap can be eliminated by writing the
LISP code with more attention to speed; at present it is written with
concern only for legibility and my programming time, with heavy use of
the fore-mentioned "special" variables and "over-modularization" of
the code resulting in many more procedure calls than really
necessary.)
.skip
3.	LISP uses a standard character set.  Essentially all
general-purpose terminals on the market today adhere pretty closely to
the ASCII standard character set.  It would be next to unthinkable for
a language designer today to propose a language that made heavy use of
a radically different character set, so this claim almost goes without
saying.
.skip
4.	LISP is interactive.  If one wants to know the value of 1+1
while "talking to" LISP, one types (PLUS 1 1) and LISP replies 2
without further ado.  If one wants to get a big job underway, one
simply invokes the top-level function of that job in exactly the same
way.  And of course one's program can always type directly to the user
and accept input from him at any time.  Perhaps more significantly,
one can interact with one's program while it is running, interrupting
to both modify and/or examine the environment.  In powerful languages
like LISP, environment examination is made more complicated by the
complexity of the environment; nevertheless LISP provides the tools
needed to explore nested contexts and complex data structures.
.skip
5.	LISP is modular.  One of the joys of programming in LISP is
that almost everything one does can be done incrementally, either on
the user's command or under program control in all cases.  If one is
running a LISP program and wants to interrupt it to write another
function, one can do so on the spot without having to re-read the
whole program back into LISP.  If one takes a dislike to the behavior
of the lexical analyzer, its behavior can be modified on the spot,
either locally or by wholesale and instantaneous replacement with a
new analyzer.  If the routine used by the top-level listen loop to
print the answer is inappropriate to the task, it can be changed in
one command; in fact, the entire top-level listen loop can be
replaced.  If a given system-defined function such as PLUS is not to
the user's taste he can simply supply his own, without having to
change every occurrence of PLUS in his program to a user-defined
name.  Even the READ function invoked by the top-level listen loop can
be replaced with a user supplied function, an advantage so important
that we afford it special treatment in the next section.
.BREAK
LISP's modularity is important not only to a single programmer
but to groups of programmers cooperating on a project.  When one
develops a LISP program for a specific application, it can be used
later as a subroutine of somebody else's program.  While this is true
to a limited extent of most languages, it holds to a much greater
extent in LISP.  When I developed a natural language system several
years ago I had in mind that I would be using it as a stand-alone
system.  However it has found use in the AI lab and in LCS as a
subroutine that other programs can call to get the translation of the
English being typed by the program's user.  In the middle of preparing
this document a Harvard graduate student working with the MACSYMA
project, Michael Genesereth, came into my office to ask me whether he
could attach my natural language front end to his MACSYMA
advice-giving program.  The task proved trivial; after a bit of
ferreting around in my files and a quick demonstration I gave him the
file and the name of the subroutine to call.  He went away, and ten
minutes later sent me a message on the computer expressing delight
that it was doing just what he needed.
.BREAK
Another example of this modularity concerns a
program-proof-checker that Steve Litvintchouk, a graduate student of
mine, has been writing in LISP.  He complained to me that entering
statements about programs into the computer was painfully slow because
he was using standard LISP notation.  So I made up a formal definition
of the notation we had been using in class, implemented it one
afternoon, loaded it into a LISP that already had Litvintchouk's
program loaded (after a few debugging runs of course) and we were then
able to talk to his program in the notation we wanted.  (Sample:
[Y:=X+5]<Y:=Y-1*>X=Y asserts that after setting Y to X+5, it is
possible by iterating Y:=Y-1 to reach a state in which X=Y.  We were
tiring of writing (([] (:= Y (+ X 5))) ((<> (* (:= Y (- Y 1)))) (= X Y)))
to express the same thing.)  The remarkable thing about this
particular exercise is that I had no idea what his code looked like at
the time as I had not then gotten around to reading it, and he had no
idea how one went about changing notation in LISP.  Yet despite this
mutual ignorance, and without making ANY changes to his code, we were
able to accomplish in a quite simple way what would require major
surgery to the given program in almost any other language.
.skip
6.	LISP is notation-independent.  Mathematically speaking, LISP
programs form a set containing "atoms" and closed under the pairing
function CONS.  How such programs are to be represented is an
implementation-dependent issue.  In any implementation there are at
least two representations, internal (consisting in the interpreted
case of a graph whose nodes are computer words and whose edges are
pointers, and in the compiled case of a string of machine
instructions) and external (consisting traditionally of fully
parenthesized prefix (forward Polish notation) expressions).  However,
this does not exhaust the possible representations of LISP programs by
any means, a point that is frequently over-looked and yet one that was
made right at the outset by McCarthy, who used what he called MLISP
notation, an algebraic notation that PL/I users would feel much more
comfortable with than the fully parenthesized prefix notation.  An
implementation of MLISP exists at Stanford, and is the notation of
choice for LISP users there.  At MIT an MLISP-like notation called
CGOL is available to the LISP user: at any time, even half-way through
running his program, he can simply say (CGOL) and from then on he can
rephrase
.begin crbreak; indent 0,4;preface 0;
βββ(QUOTIENT (PLUS (MINUS B) (SQRT (DIFFERENCE (EXPT B 2)(TIMES 4 A C)))) (TIMES 2 A))
as  
βββ(-b+sqrt(b**2-4*a*c))/(2*a)
or
βββ(MAPCAR '(LAMBDA (I J) (PRINT (CAT '|Buy | I '| for | J '| dollars.|))) SHOPPINGLIST PRICELIST)
as
βββfor i in shoppinglist, j in pricelist do
ββββββprint "Buy " ↑ i ↑ " for " ↑ j ↑ " dollars."
.end continue;
and so on.  The versatility of LISP in comparison to most other
programming languages becomes more apparent in this notation because a
more direct comparison is possible without the distraction of having
to allow for radically different styles of notation.  (An aside:
although all programming languages deserving of the name can express
the first of the above examples, very few can cope with the second
quite so directly.)
.BREAK
The CGOL notation inherits LISP's modularity, in that it can
be extended painlessly by the user even while in the middle of running
a program.  This legacy of LISP's puts this algebraic notation ahead
of almost all other available algebraic programming languages with
respect to syntactic extensibility.  Only a few research systems come
close to this level of convenience, such as Bell Laboratories'
recently developed YACC (Yet Another Compiler-Compiler) system, a
version of which has been developed by Alan Snyder at MIT and is used
as the "front-end" of Barbara Liskov's CLU language at MIT.  Even
these advanced systems do not offer fast incremental extensibility of
this syntactic front-end to LISP [6,8].
.BREAK
It may be instructive to compare an ALGOL program taken
verbatim from the Communications of the Association for Computing
Machinery, Algorithm 482 [3], with its rendering in this algebraic
dialect of LISP.  We give the ALGOL version first, changing only its
comment section for the sake of brevity.
comment We are given a set of towns numbered 1 to n.  There are k one-way
roads leading out of each town in such a way that if you ever go on a
trip you can always get back home again, though not necessarily by
retracing your steps.  However, it is not guaranteed that you can
always get to the town of your choice.  The problem is to group the
towns into equivalence classes of mutually accessible towns.
.BREAK
The roads are represented by an array im[1:n, 1:k] such that
im[r,q] is the q-th town accessible from town r.  You are given two
arrays ind[1:n] and orb[1:n] to store the results in.  Town i is to be
in the ind[i]-th equivalence class.  Orb[i] is a list of towns
arranged so that each equivalence class is in a contiguous block; the
first town of each block is stored with its sign bit complemented (in
particular town 1 will appear in orb[1] as -1) to distinguish the
beginning of the block. 
.BREAK
(The problem was stated in CACM in group-theoretic terms, with
orb referring to orbits of group elements, but the ALGOL solution
given in CACM solves the more general problem we have just described.)
.begin crbreak; indent 0,4; algol; preface 0;
procedure orbits(ind, orb, im, n, k);
ββvalue n, k; integer n, k;
ββinteger array ind, orb, im;
begin
ββinteger q, r, s, j, nt, ns, norb;
ββfor j := 1 step 1 until n do ind[j] := 0;
ββnorb := 0; ns := 1;
ββfor r := 1 step 1 until n do if ind[r] = 0 then
ββbegin
ββββnorb := norb + 1; ind[r] := norb;
ββββnt := ns; orb[ns] := -r; s := r;
a:
ββββns := ns + 1;
ββββfor j := 1 step 1 until k do
ββββbegin
ββββββq := im[s,j];
ββββββif ind[q] = 0 then
ββββββbegin
ββββββββnt := nt + 1; orb[nt] := q; ind[q] := norb
ββββββend
ββββend;
ββββif ns ≤ nt then
ββββbegin s := orb[ns]; go to a end
ββend
end
.end
The following is the LISP rendering of the above procedure,
using the algebraic dialect.  For direct comparison we have adhered as
closely as possible to the layout of the above program.
.begin crbreak; indent 0,4; preface 0;
define "ORBITS"(ind, orb, im, n, k);
(
ββnew q, r, s, j, nt, ns, norb;
ββfor j in 1 to n do ind(j) := 0;
ββnorb := 0; ns := 1;
ββfor r in 1 to n do if ind(r) = 0 then
ββ(prog;		α% necessitated by the presence of (ugh) goto α%
ββββnorb := norb + 1; ind(r) := norb;
ββββnt := ns; orb(ns) := -r; s := r;
a;
ββββns := ns + 1;
ββββfor j in 1 to k do
ββββ(
ββββββq := im(s,j);
ββββββif ind(q) = 0 then
ββββββ(
ββββββββnt := nt + 1; orb(nt) := q; ind(q) := norb
ββββββ)
ββββ);
ββββif ns <= nt then
ββββ( s := orb(ns); go a )
ββ)
)
.end
The only differences in this example are:
.begin crbreak; turn on "\"; tabs 18,25;preface 0; indent 0,27
.algol
ββββALGOL	\ββββLISP
a[b]		\a(b)	\(arrays)
begin end	\( )	\(block delimiters)
integer		\new	\(type declarations inessential)
procedure	\define
ββ(and related text)	\ββ(and related text)
for i := 1 step 1	\for i in 1 to n
ββuntil n
a:  (and associated	\a; (and associated
ββgoto)		\ββprog and go)
value		\redundant (arrays may be values in LISP)
≤		\<=	(≥ not in ASCII standard)
.end
Except for %3value%* and ≤, the first of which is redundant in
LISP and the second of which is not available in the standard ASCII
character set, none of these differences are essential; the CGOL
notation, being user extensible, can be modified either by the
individual user, or by the system programmers when a sufficiently
large demand exists, to permit the use of the first seven of the above
ALGOL constructs, at least for this example (where we were fortunate
that we could translate ALGOL's %3goto%* directly; %3goto%*'s out of blocks
require a more involved translation into LISP in general, as does call
by name.)  However I do not foresee frequent use being made of such
modifications to the notation.
.BREAK
The above comparison is a little like having a race between a
Ford and a Porsche where the drivers are required to behave
identically.  After a few seconds the Porsche driver starts to grumble
about being in third gear when he should be in fifth.  In the above
example there is some clumsy programming going on that is the result
of programming in a language that does not provide adequately for
irregularly structured data.  Actually, the input of this example (the
array im) is regularly structured, but the result (the array orb)
attempts clumsily (using the sign bits of its entries) to represent
the irregularly structured answer.
.BREAK
We give below another version of the same algorithm, this time
relaxing the constraint that we have to mimic the ALGOL solution as
closely as possible.  First we observe that the array im is really the
only input data required.  Second, we suggest that im be represented
as a vector of lists, allowing a variable number of roads to leave
each town.  (In the group-theoretic special case of this problem, k is
fixed, corresponding to having k generators of an n element group, but
the solution given in CACM makes no essential use of k being fixed.) 
Third, we suggest that the answer be an array (corresponding to ind in
the above program) whose i-th element is the list of towns accessible
from town i (numbering these equivalence lists as in the above
programs seems pointless).
.BREAK
All variables except adi (array dimensions of im) correspond
to variables used in the above programs, though they may not be of the
same type.
.begin crbreak; indent 0,4;preface 0;
define "ORBITS" im;
let adi = arraydims im;
let ind = arrayα{nil . adi}, n = cadr adi - 1, nt = nil;
for r in 1 to n do if null ind(r) then
ββ(ind(r) := nt := [r];
βββfor s in ind(r) do
ββββββfor q in im(s) do if null ind(q) then
ββββββββ(ind(q) := ind(r); cdr nt := [q]; nt := cdr nt));
ind
.end
The outermost for-loop looks for towns not yet in equivalence
classes (LISP initializes untyped arrays to NIL, whence the NULL
test).  When a new town r is found, a length-one equivalence list [r]
is started for it, and nt is set to the last LISP cell of the list
(which initially is also the first).  Then for each town s on the
list, towns reachable from s that as yet belong to no list are put at
the end of this list.  (Since "for s in ind(r)" does not make a
separate copy of the list ind(r) before scanning it, putting more
towns on the end of the list forces the for-loop to consider those
towns as well, which is what we want here.  Though this is not good
LISP style, it is how one would use LISP to do what was done in the
ALGOL program, which is not good style either.)  When all towns have
been put into classes, the array ind is returned.  To use the
subroutine on input array x to find out what towns are accessible from
town i, say "(orbits x)(i)" which will compute the ind array and then
apply it to i.  This of course is an inefficient use of ORBITS;
usually one will say "x := orbits y" and later say "x(i)" for each i
of interest.
.BREAK
For those readers wondering how hard I had to look to find an
example better coded in LISP than ALGOL, I should say that I simply
selected the most recent short ALGOL contribution to CACM's algorithms
section that I could find on my bookshelf.  I originally had not
intended to give the second LISP version, but could not resist it once
I figured out what the algorithm was up to.
.BREAK
CGOL is not the only algebraic dialect of LISP available at
MIT.  MACSYMA users also use an MLISP-like algebraic notation - in
fact MACSYMA's parser is just the CGOL parser modified (by Michael
Genesereth) to handle typed expressions.  Unlike CGOL in plain LISP,
MACSYMA notation is the default language for MACSYMA users.
.BREAK
It must be admitted that any notational change to LISP raises
the question of what constitutes a programming language.  Must one buy
lexicon, syntax, semantics and object code as a package, or can one
shop around like a purchaser of a component stereo?  The argument of
this section has assumed that one %2can%* shop around, but I realize that
while component stereos may make sense to an electrical engineer, the
concept of component languages may require some getting used to.  I
feel that this issue drives home the disadvantage of most languages,
that you cannot use it for its good features without also having to
accept its bad features.  This situation has encouraged an attitude
among language users that permits arguments of the form, "We can't
have X because it has a bad feature, namely its syntax."  As the
computer-using community matures, it should grow more accustomed to
the idea of purchasing language components and assembling them into
their "ideal" system.  As a spin-off from this sort of technology, we
may hope to see a decrease in the number of languages available, a
number which from this point of view we can attribute to the
multiplicative way in which options must increase when you cannot
order systems component by component.  For example, if the community
demands two kinds of lexicons, two kinds of syntax, two kinds of
semantics and two kinds of code-generators, the market need supply
only eight components in place of sixteen systems.  Any increase in
the sizes of the component options results in a rapid widening of this
gap.
.BREAK
In this context the question of whether to choose a widely
used language must be restated as whether to choose a widely used
component.  This question is perhaps most important for the syntax
component, which for the user is as at least as visible as any other
component.  Although I suggested above that CGOL or MACSYMA notation
is a possibility, other notations are equally possible, such as the
very widely known ALGOL notation.  In fact, an ALGOL front-end has
been built for LISP along the lines of the CGOL front-end (but with
more attention paid to preserving the semantics of ALGOL than is
implicit in our translation of the ALGOL example above), and if the
question of whether the notation was widely known became a serious
issue, the replacement of CGOL or MACSYMA notation by ALGOL notation
is straightforward, modulo tortuous implementation when the (rarely
used in practice) environment-handling capability of ALGOL is given
full throttle.  Our personal feeling is that the CGOL notation is
already so close to ALGOL notation when it comes to those things one
regularly wants to say in ALGOL that to insist on one-hundred-percent
ALGOL notation is gilding the lily for almost all applications.
.BREAK
LISP's independence of choice of notation may be of value in
an educational environment where, although a commitment to a single
language may have already been made, individual instructors may
nevertheless have a requirement for a different notation.  LISP's
ability to change notations in midstream without having to change
languages reduces the overhead associated with maintaining several
entire languages and their supporting maintenance teams and other
paraphernalia.  For example, if APL were needed on occasion, it would
not be impossible to embed it in LISP; indeed a very compact
definition of APL is possible in LISP.  However it would seem only
fair to ask the users of such 
.skip
7.	LISP is applicative.  That is, one can write non-trivial
programs in LISP using only functional application that in other
languages would have to be written iteratively or recursively.  The
two LISP functions (strictly, functionals or combinators) that supply
this power are MAPCAR and APPLY.  MAPCAR permits a function to be
applied to the elements of a list one at a time (coordinate-wise
operation) while APPLY permits an operation such as PLUS to be applied
to all the elements of the list (APL's notion of reduction, written
+/a).  APL, like LISP, offers non-applicative features such as
assignment and goto, but its users are strongly encouraged to rely on
the applicative part of APL, and (presumably) to ensure that this
happens APL offers a bare minimum of non-applicative 
control structures.  A significant benefit of this style is
that reasoning about such programs can be done in the same algebraic
formalism that we have all been raised on since birth, instead of
having to invent systems of logic especially to cope with the
non-algebraic control structures of conventional programming
languages.  For example, knowing that + is associative even when
applied to equal-length vectors as opposed to scalars, we can
immediately see that (u+v)+w computes the same vector as u+(v+w),
whereas we may have to argue more indirectly about the effect of the
corresponding two programs in a non-applicative (in this case
non-vector-manipulating) language.  Vector spaces have been well
studied and their properties carry over readily to reasoning about APL
programs.
.BREAK
Let us give some examples where LISP can be used as an
applicative language.  The CGOL notation a[[b]] for (MAPCAR 'a b)
helps to emphasize the functional nature of MAPCAR, inasmuch as
a[[[b0, b1, b2]]] (where [b0, b1, b2] is the list being operated on)
means simply the list [a(b0), a(b1), a(b2)] .  (The reason for two
brackets is that two separate operations are really invoked by a[[b]],
which is equivalent to a[x] where x is [b] (the list whose only
element is b).  Thus when u and v are added coordinatewise using
plus[[u,v]], in fact the operation is plus[x] where x is the
two-element list [u,v].)  Likewise the notation aα{b} for (APPLY 'a b)
emphasizes that a is just being applied to the list of arguments b. 
Thus given a list b of numbers, plusα{b} yields its sum, corresponding
to +/b in APL.  Given two lists a and b, plus[[a,b]] yields the list
which is the coordinate-wise sum of the two lists, corresponding to
APL's (syntactically more succinct but no more or less applicative)
a+b.  Thus to compute the inner product of two vectors (represented as
lists though the semantics of LISP does not forbid lists being
represented internally as vectors when appropriate) it suffices to
write plusα{times[[a,b]]}, corresponding to APL's +/a*b.  One way to
write a one-line matrix multiplication routine in LISP (yes, APL has
no monopoly on one-liners) would be
.begin preface 0; indent 0,4;
ββfor i in x collect for j in list[y] collect plusα{times[[x,y]]} .
.end continue
(Here list[y] transposes the list of lists y, representing a
matrix stored as a list of rows, for reasons about as obscure as those
that account for a variety of APL techniques such as conditional
goto.  The reader who followed our explanation earlier of what a[b]
did will realize that list[y] is equivalent to list[[y0,y1,...]] where
y = [y0,y1,...].)  In this example I have deliberately avoided the
equivalent more succinct but less transparent syntactic variant of the
above,
.begin preface 0; indent 0,4;
ββ(\i;(\j;plusα{times[[i,j]]})[[list[y]]])[[x]]
.end continue
This is an example of where LISP's versatility permits the user to
avoid the APL trap of being forced to write code applicatively even
when it might be better understood by writing it dynamically using a
"for" loop.  (Strictly speaking, the APL user does have the option of
a dynamic solution, as goto exists in the language; however there are
dynamic solutions and dynamic solutions, and code written with goto's
rarely constitutes an improvement over other arcane solutions to
programming tasks.)
.BREAK
In some respects LISP's applicative ability is superior to
APL's.  APL lacks a specific operator that permits coordinate-wise
application of a scalar operator, but rather relies on the fact that a
scalar operation is being applied to a vector to deduce that
coordinate-wise operation is called for.  When a user has defined an
operation that applies equally well to scalars and vectors, he cannot
specify to APL whether or not he wants to apply his operation to the
list as an entity or coordinatewise to its individual components.  In
LISP one distinguishes these cases explicitly as a(b) versus a[[b]].
.skip;
8.	LISP is widely used in academia.  In a large portion of the
academic computing community LISP is either a first or a second
language.   I received last week a letter from Gene Freuder, a recent
MIT graduate now teaching at Indiana, where he is their AI
representative.  He was happy to report that in his department
"everyone speaks LISP as a mother tongue."  While one might not be
surprised to hear this about a department with a heavy AI bias, it is
a tribute to LISP's ubiquity that it should be so honored in a
department noted primarily for its work on programming languages and
multiple-valued logic.
.skip
9.	LISP is used by half the MIT Computer Science faculty.  Thus
choosing LISP as the main departmental language, if one language is to
be chosen ueber alles, would seem to involve the least upheaval. 
Further, LISP as a high quality language attracts high quality
maintenance personnel.  LISP has been maintained here not only by Jon
L. White, a very experienced LISP systems programmer, but by some of
the sharpest graduate students in the world.  Guy L. Steele, winner of
the 1975 George Forsythe student paper competition [9], the main
student-paper competition in the computer-science world, has been a
shining example of such help for several years dating back to his
undergraduate days.  The situation seems simply to be that the best
languages attract the best students.  Unless MIT suddenly experiences
a dearth of good students, a fate few of us want even to contemplate,
this high quality maintenance should continue at or near its present
enviably high level.
.skip
10.	No other language enjoys all the above advantages of LISP.
This remains true even if advantages 2 and 4 are omitted.  Let us
argue this point on a language-by-language basis, choosing (at the
risk of offending all whose languages have been omitted) FORTRAN,
COBOL, ALGOL, PL/I, APL, ALGOL 68 and PASCAL.  In the following we
omit reference to items 2, 4, and 9; the first two are easy to satisfy
while the last is obviously impossible.
.break
FORTRAN:	This fails on items 1, 5, 6 and 7.  FORTRAN's storage
allocation facilities and control primitives are too rudimentary to
make FORTRAN useful outside the domain of numerical arrays, for which
it was designed.  By bending over backwards one can do anything in
FORTRAN, as in any universal language (in Turing's sense); for example
Joseph Weizenbaum implemented SLIP, a list processing language, in
FORTRAN, and it is the language used for symbol manipulation at Bell
Laboratories.  However, one is sufficiently hemmed in by petty
restrictions and inadequate data and control structures that no very
strong case can be made for it.
.break
COBOL.	COBOL has something to offer academia that FORTRAN lacks, and
that is a "data division" (to use COBOL terminology) that permits the
user to define a rich variety of data types.  This can lead to
considerable simplification of the "program division," since the COBOL
compiler can automatically make many decisions about where to put
things and how to represent them.  Unfortunately COBOL's data types
are rich in about the same sense that an Eskimo finds a richness of
snow varieties in the Arctic; this richness goes unappreciated in
other climates, and COBOL's concern with business data processing
makes it too narrow for use in other environments.  We can rule out
COBOL on the same grounds as FORTRAN, together with item 8.
.break
ALGOL.	A discussion earlier (item 6) of LISP's ability to disguise
itself as an ALGOL-like language revealed a serious lack of
versatility in ALGOL.  Actually, ALGOL's control structures are
remarkably powerful; one can do truly astonishing things with ALGOL's
goto statement, such as jumping out of a procedure body that has
called itself recursively to a great depth, resulting in exiting from
all those levels of recursion in response to one %3goto%*.  Also ALGOL
offers call by name, which permits such useful constructs as Jensen's
device for implementing a summation operator.  Unfortunately these
strengths of ALGOL do not make up for its weakness in the versatility
of its data types.  ALGOL fails on items 1, 3 (to a small but not
terribly important extent), 5, 6, and 7.
.break
PL/I.	PL/I is nothing if not versatile.  At least that is what IBM
had in mind when they designed it.  However, to be versatile without
being modular is to be a super-market, where sometimes you spend more
time looking for the aisle you need than all the other operations
combined.  PL/I fails on items 5, 6 and 7, as well as 1 in my opinion.
.break
APL.	APL passes strongly on item 7 (applicative), though not
without a black mark for being unable to distinguish a(b) from a[[b]]
(using CGOL notation).  For what it attempts to be, namely a
vector-manipulating language, it also does well on item 1.  Though we
promised to omit reference to item 4 (interactive), this is a very
strong feature of APL, and supplied me with my one reason to use APL
considerably during a summer visit to IBM.  Unfortunately, little of
my work happened to fit the vector mold very well, despite the fact
that most of it was heavily numerical, and I found myself from time to
time using the embryonic 360 LISP system maintained by Fred Blair at
IBM, on the ground that the additional time I had to spend running
back and forth between the CP/CMS editor and LISP was made up for by
the considerably decreased programming time in LISP.  Thus I would
fail APL on item 1, though not as seriously as the above languages.
What really makes APL totally unacceptable is the insistence on a
character set so out of touch with the ASCII standard that the
department would be locked into an unacceptably inflexible (not to say
expensive) situation if it were to generally adopt APL.  APL also
fails on 5 and 6.
.break
ALGOL 68.	This language is full of nice ideas.  It has been
carefully thought about by people with a concern for elegance and
mathematical precision.  Unfortunately the former has been sacrificed
to the latter, and to learn ALGOL 68 requires considerable patience
while one discovers the correspondence between one's programming
intuition and the picturesque vocabulary of an ALGOL 68 programming
guide (not to be confused with the language's formal definition, which
is written in a relatively inaccessible meta-language).  ALGOL 68
fails on items 6, 7 and 8.
.break
PASCAL.	 Nicklaus Wirth sensibly designed PASCAL to be simple in
concept, easy to implement, efficient, yet versatile in its data
types. Moreover, he saw to it that a good implementation on a machine
commonly found in universities (a large CDC machine) was made
available.  As a result, PASCAL has attracted the attention of many
computer science departments as being an ideal pedagogical language. 
PASCAL's greatest drawback is the extent to which Wirth had to
compromise to achieve ease of implementation.  As a result, PASCAL
(like every other language above) lacks the first-class-citizen
property that makes LISP so pleasant to use yet simple to implement in
the event that you are willing to forego efficiency on some of the
data types.  I believe that this concession to efficiency, while it
has many merits, detracts considerably from PASCAL's otherwise
excellent versatility.  Nevertheless, PASCAL remains among the more
attractive possibilities.
.skip 200;
B.  DRAWBACKS OF LISP.
.BREAK
Most of the complaints of this section are
implementation-specific and do not inhere in the LISP language itself.
The one major exception to this is LISP's typelessness.  It is
unlikely that future implementations of LISP will clear up this issue
without introducing substantial incompatibilities with existing LISP
software.  Moreover, many feel that typelessness is more virtue than
vice.  In contrast, The various complaints about the implementation
cannot be taken seriously from a long-term stand-point.  Other
implementations of LISP are presently in an experimental stage, one in
hardware (Richard Greenblatt's LISP machine) and one using the lexical
scoping of the lambda calculus (Guy Steele and Gerald Sussman).  Thus
implementation-specific properties of LISP are at present in a state
of flux, and taking them into account in deciding that LISP was
inadequate would be a case of throwing out the baby with the
bathwater.  Let us now begin with my one implementation-independent
complaint.
.BREAK
LISP does not in any systematic way permit the user to specify
the types of his data and variables.  In fact some types are
implemented directly as other types without LISP being able to tell
which type is intended. For example, NIL serves double duty as the
boolean FALSE and the empty list, as well as being recognized by LISP
as an atom (though not one that can be used as a variable).  And bit
vectors are just single-precision integers; indeed only the presence
of bit-manipulating operations permits LISP to claim that it has the
type bit vector.  Though this typelessness of LISP has an advantage in
permitting the user to save programming time by not having to declare
types, there remains the fact that many bugs are detectable because
they violate type constraints.  These violations will be caught by the
interpreter (if at all) only when the offending portion of the code is
actually run; for this reason some LISP users compile their newly
written code before or even instead of debugging it interpretively as
a first debugging step on the ground that at least the compiler does a
fair to moderate job of detecting type violations.  This philosophy of
tight control over types is at the heart of the design philosophy of
Barbara Liskov's CLU language at MIT along with similar research
languages at other campuses such as Carnegie-Mellon's ALPHARD
language.
.BREAK
Another source of troubles with LISP is the classic FUNARG
problem, so named by Joel Moses [4] in an early discussion of the
problem.  Although a completely correct handling of this problem is
not at the top of all users' lists of demands, it is for some; also,
the formal description of LISP is simplified if one assumes that the
problem, which involves being able to pass around program-environment
pairs just like any other data, is properly taken care of.  As things
stand at present, the partial solution implemented in MACLISP is
better described operationally, leading to a more clumsy description
of LISP than is possible otherwise.  Several plausible solutions
(by Richard Greenblatt, Henry Baker, Guy Steele and Gerald Sussman) are
in the air, and one may soon find its way into MACLISP.
.BREAK
A much less serious complaint is that the user may not specify
a lower bound for any array dimension other than 0.  To an extent this
objection can be overcome using the notational flexibility discussed
in section 6 by permitting a(i) to denote (A (PLUS I 7)) or whatever.
Another complaint is that with the bit-vector data type, LISP itself
only offers 36-bit bit vectors.  However, LIBLSP (the public LISP
software library on the ITS machines) offers a package written by
Henry Baker that confers efficient unlimited-length bit-vector
processing capability on LISP.  This package really ought to be
available directly to LISP users.  In my LINGOL natural language
system, which does a considerable amount of set-oriented processing
involving set intersection and union, bit vectors have supplied a very
efficient implementation of sets.
.BREAK
A continual source of petty irritation for me is the compiler,
which overlooks many simple optimizations.  However, my pique
notwithstanding, the compiler is probably the best LISP compiler
available anywhere as it does a remarkably good job of optimization
considering LISP's versatility.  No matter what language the
department settles on, if it is as powerful as LISP, people will be
complaining about overlooked "obvious" optimizations for quite a
while, possibly for ever.
.BREAK
One can come up with a variety of minor complaints of this
ilk, but beyond the first two major complaints about LISP's
typelessness (regarded by many others as a virtue) and lack of
environment-manipulating capability, I personally am pretty satisfied
with the language.
.skip;
C.  DEPARTMENTAL REQUIREMENTS.
.BREAK
Though the department has asked for a good educational
language, there is no harm (if we are considering LISP) in asking that
the research needs of the department also be considered.  Here are a
number of headings (suggested to me by Ronald Rivest) under which one
may ask about the utility of LISP.

1. Desktop calculators.  As pointed out before, one need merely type
1+2*3 followed by a termination character to get the answer 7.
Although my secretary cannot program she has used LISP regularly for
two years for precisely this application, even though the bulk of her
arithmetic is just adding up numbers.  In fact almost any expression
that can be typed on an SR-51, say, can be typed almost verbatim to
LISP.  Moreover, the comparatively unlimited storage of LISP is
available for storing intermediate results.  Thus a LISP terminal
consisting of a calculator-sized keyboard and a 15-digit display would
already provide enormous power.  Going to a 30-character alphanumeric
display would increase the utility of such a terminal considerably. 
Such terminals could be so cheap that each office in the building
could have two or more if necessary.  With reasonable system design,
the formalities of logging such terminals on and off could be
dispensed with.  Thus LISP would be available as a powerful
replacement for programmable calculators, yet lacking none of their
convenience.  The possibility exists of making such terminals
completely portable, at least within the building, relying on a radio
link for contact with the department's system.

2.  Number-crunching.  We have already referred to Bers' Plasma
Dynamics group, in the section on efficiency.  This supplies an
example of where LISP is already in use within the department for
"number-crunching" on a large scale.

3.  Classroom language.  Not surprisingly, LISP is the classroom
language for Patrick Winston's AI course.  Perhaps more surprisingly
is that it is also the language for my undergraduate algorithms
course, which teaches the sort of material one finds in Donald Knuth's
volumes on algorithms.  We deal with graph and matrix algorithms, bit
vector algorithms, integer and real arithmetic, storage management,
information organization and retrieval, and sorting.  The language
(which I call "The 6.046 programming language" so that any opponents
of LISP in the class won't take offence - they don't recognize LISP in
its algebraic dialect) is spelled out in a class handout and students
are required to stick to it.  This gives the students a
simple-to-learn yet versatile and well-defined language that simplifies
our grading.  The versatility of LISP simplifies many of the
algorithms I teach, and at the same time makes it possible for us to
run a student's algorithm on the computer if neither the T.A.'s nor I
can understand what it is supposed to be doing, a feature we
occasionally take advantage of.  It is regrettable that we cannot
offer unlimited access to LISP for the students, a fact we have to
keep perpetually in mind when setting and grading problems requiring
some programming.

4.  Publication Language.  This is one area where the case for LISP is
not strong.  Although LISP's standard notation is popular with many
LISP users, it does take sufficient getting used to that it is not an
appropriate publication language except in AI circles, since outside
of AI the world is very algebraically oriented.  The fact that an
algebraic dialect for LISP only helps if that dialect is well known,
or at least understandable without lots of explanation, which is not
at present the case for any of the MLISP, CGOL or MACSYMA dialects. 
One solution is to translate the algebraic dialect into a well-known
language; this may only be possible if some restraint is used in
taking advantage of LISP's versatility.  Another possibility is to go
ahead and use an algebraic dialect of full-blown LISP on the
chauvinistically evangelical ground that the rest of the world ought
to learn such a lovely language, especially when they aren't being
asked to suffer the fully parenthesized notation.  This issue should
be brought up in any defense of PASCAL, where it is more reasonable at
present to assume that the reader can follow PASCAL code.
.BREAK
In summary, I would say very simply that LISP would make an
excellent departmental language.  All things considered, it has little
serious competition from any language except PASCAL, and even that
competition is minimal.  At this point it is appropriate to include
the %2ad hominem%* argument that LISP, an MIT product, has had a
considerable impact on the academic computing community over the past
decade and a half, and along with magnetic core storage, CTSS, MULTICS
and MACSYMA has been responsible for making MIT close to the world's
most influential source of Computer Science ideas.
.skip 2
.once center; select 3;
Bibliography.

.indent 0,5;
[1]	Fateman, Richard J. "Reply to an Editorial." SIGSAM Bulletin
25, 9-11.  (March 1973).

[2]	Hewitt, C. E., P. Bishop, and R. Steiger.  "A Universal
Modular ACTOR Formalism for Artificial Intelligence," Proc. IJCAI
3, p. 235. 1973.

[3]	McKay, John and E. Regener.  "Transitivity Sets."  Algorithm
482, CACM 17, 8, 470.  (August 1974).

[4]	Moses, Joel. "The Function of FUNCTION in LISP." AI Memo 199,
MIT AI Lab (Cambridge, June 1970).

[5]	Popplestone, R. J.  "The Design Philosophy of POP-2."  Machine
Intelligence 3 (ed. D. Michie), 393-402, Edinburgh U. Press, 1968.

[6]	Pratt, V. R.  "Top Down Operator Precedence."  Proc. ACM
SIGACT/SIGPLAN Conf. on Principles of Programming Languages (POPL 1),
Boston.  (October 1973).

[7]	--------.  "A Linguistics Oriented Programming Language."
Proc. 3rd International Joint Conference on AI, Stanford, 1973.

[8]	--------.  "CGOL - an Alternative External Representation
For LISP Users."  MIT AI Lab Working Paper 89.  1976.

[9]	Steele, Guy Lewis Jr. "Multiprocessing Compactifying Garbage
Collection." Comm. ACM 18, 9, 495-508.  (September 1975).